package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;
import cn.pugle.oj.catalog.TwoProblem;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * O(n)时间
 * 操, target里可以有重复字母
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC76 implements TwoProblem, Greedy {
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";
        Map<Integer, List<Integer>> targetChars = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            targetChars.put((int) t.charAt(i), new LinkedList<>());
        }
        for (int i = 0; i < s.length(); i++) {
            if (targetChars.containsKey((int) s.charAt(i))) {
                targetChars.get((int) s.charAt(i)).add(i);
            }
        }
        //from left to right
        int leftMax = 0;
        while (leftMax < s.length()) {
            if (targetChars.containsKey((int) s.charAt(leftMax))) {
                List<Integer> list = targetChars.get((int) s.charAt(leftMax));
                if (list.size() == 1) {
                    break;
                } else {
                    Integer removed = list.remove(0);
                    assert removed == leftMax;
                    leftMax++;
                }
            } else {
                leftMax++;
            }
        }
        int rightMax = s.length() - 1;
        while (rightMax > leftMax) {
            if (targetChars.containsKey((int) s.charAt(rightMax))) {
                List<Integer> list = targetChars.get((int) s.charAt(rightMax));
                if (list.size() == 1) {
                    break;
                } else {
                    Integer removed = list.remove(list.size() - 1);
                    assert removed == rightMax;
                    rightMax--;
                }
            } else {
                rightMax--;
            }
        }
        return s.substring(leftMax, rightMax + 1);
    }

    public static void main(String[] args) {
//        System.out.println(new LC76().minWindow("ADOBECODEBANC", "ABC"));
//        System.out.println(new LC76().minWindow("AZZZZZAxBxCZZZZZCZ", "ABC"));
        System.out.println(new LC76().minWindow("a", "aa"));
    }
}
